package ljl.alg.wangzheng_camp.round1.twopointers;

import java.util.*;

/**
 * 输入: nums = [5,6,5,6], target = 11
 * 输出: [[5,6],[5,6]]
 *
 * */
public class _16_24_pair_sum {
    
    /*
    *
    * */
    public List<List<Integer>> pairSums(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int sum = nums[l] + nums[r];
            if (sum == target) {
                res.add(Arrays.asList(nums[l], nums[r]));
                // 这两个条件别忘了
                r--;
                l++;
            } else if (sum < target) l++;
            else r--;
        }
        return res;
    }
    
    /*
    * 试试 hashtable 的解决方案
    * */
    public List<List<Integer>> pairSums2(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            int pair = target - num;
            if (count.containsKey(pair)) {
                res.add(Arrays.asList(num, pair));
                if (count.get(pair) == 1) count.remove(pair);
                else count.put(pair, count.get(pair) - 1);
            } else {
                count.put(num, count.getOrDefault(num, 0) + 1);
            }
        }
        return res;
    }
    
    
}
